package com.jhy.new2025.string;

public class RepeatedSubstringPattern {
    /**
     * 给定一个非空的字符串 s ，检查是否可以通过由它的一个子串重复多次构成。
     *
     * @param s
     * @return
     */
    public static boolean repeatedSubstringPattern(String s) {
        /**
         * 可以使用kmp算法
         */

        /**
         * 怎么求重复的子串就是 最长相同的前后缀不包含的那个子串
         */
        int[] next = new int[s.length()];
        getNext(next, s);
        int length = s.length();
        return next[length - 1] != -1 && length % ((length - (next[length - 1] + 1))) == 0;
    }

    public static void getNext(int[] next, String str) {
        // 初始化
        int i = -1;
        next[0] = -1;
        // 前后缀不相等的情况
        for (int j = 1; j < str.length(); j++) {
            while (i >= 0 && str.charAt(i + 1) != str.charAt(j)) {
                i = next[i];
            }
            // 前后缀相等的情况
            if (str.charAt(i + 1) == str.charAt(j)) {
                i++;
            }
            next[j] = i;
        }


    }

    public static void main(String[] args) {
        String str = "abac";
        int[] next = new int[str.length()];
        getNext(next, str);
        System.out.println(next[-1]);
    }

}
